Ordered Sets

#Ordered Sets| 来源: 网络整理| 查看: 265

Ordered Sets thomasalspaugh.org/pub/fnd/orderedSet.html

Home

Foundations home

Sets Relations Correspondences Ordered Sets Lattices Graphs Powersets Binary Strings Logic AIA Greek

Glossary Abstracts Argument Inquiry Cycle Legal Relations Presentations

Elicitation Glossaries Goals i* SCR Tracing

Alloy MSCs Regular Exprs.

Design Patterns Javadoc Java Packages Java Types

(X)HTML XML Schemas XSLT

Figure 2 The powerset of {a, b, c}, ordered by ⊆

Figure 1 The integers, totally ordered by ≤; a chain

Figure 3 Incomparable items forming an antichain

Figure 6 The conjunctions of any of p, q, and r, ordered by implication

Figure 5 The binary strings no longer than 3, ordered by the prefix relation ≤

Figure 4 Part of the java.util inheritance structure

Figure 8 The dual of the ordered set in Figure 7

Figure 7 The positive integers to 15, ordered by the divisibility relation

Let P be a set and ⊑ be a (partial) order on P. Then P and ⊑ form a (partially) ordered set.

If the order is total, so that no two elements of P are incomparable, then the ordered set is a totally ordered set. Totally ordered sets are the ones people are first familiar with. See Figure 1 for an example.

A totally ordered set is also termed a chain.

If the order is partial, so that P has two or more incomparable elements, then the ordered set is a partially ordered set. See Figure 2 for an example.

At the other extreme, if no two elements are comparable unless they are equal, then the ordered set is an antichain. See Figure 3.

On any set, = is an order; this is termed the discrete order on the set. Any set ordered by = forms an antichain.

It is common for people to refer briefly though inaccurately to an ordered set as an order, to a totally ordered set as a total order, and to a partially ordered set as a partial order. It is usually clear by context whether "order" refers literally to an order (an order relation) or by synecdoche to an ordered set.

Examples:

The integers with ≤ form an ordered set (see Figure 1). ≤ is a total order on the integers, so this ordered set is a chain. Any powerset with ⊆ forms an ordered set (see Figure 2). This is a partially ordered set because not all subsets are related by ⊆, for example {a} || {b, r}. A set of unrelated items, ordered by =, is the discrete order on that set and forms an antichain (see Figure 3). The classes in java.util with the subclass relation form an ordered set (see Figure 4). This set is partially ordered, because not all classes in the set are related by the subclass relations (for example, Vector and HashSet are not related and are thus incomparable: Vector || HashSet). A set of binary strings with the prefix relation forms an ordered set (see Figure 5). This is set is partially ordered because not all strings are related by the prefix relation, for example 01 || 10. The (non-empty) conjunctions of any of the propositions p, q, and r, ordered by implication, form an ordered set (see Figure 6). In this set, p∧q implies q, but p∧q neither implies nor is implied by q∧r, so p∧q and q∧r are incomparable (p∧q # q∧r) . The positive integers N with the divisibility relation form an ordered set. The divisibility relation relates m to n if m divides n, written m | n. Thus 2 | 6, and 3 | 6 but not 4 | 6 (i.e., 4 and 6 are incomparable, written 4 || 6) because 4 does not divide 6. And for any n∈N, 1 | n and n | n. A part of this ordered set is shown in Figure 7. Duality

Each ordered set P corresponds to another ordered set P∂, the dual of P, defined by: y⊑x in P∂ iff x⊑y in P.

Each statement Φ about P corresponds to a dual statement Φ∂ about P∂. Φ∂ is obtained by replacing each occurrence of ⊑ in Φ by ⊒, and each occurrence of ⊒ in Φ by ⊑. Φ is true about P if and only if Φ∂ is true about P∂. Generalizing, it can be shown that if a statement Φ is true about all ordered sets, then its dual statement Φ∂ is also true. This assertion is the Duality Principle.

Pairs of dual concepts that are defined in terms of ⊑ and ⊒ (such as upper bound and lower bound, below), are also exchanged in dual statements.

Example: Let Q be the ordered set shown in Figure 7, in which ⊑ is the integer divides relation, with the divisor "lower than" the dividend. Then the ordered set of the positive integers to 15 ordered by the converse of divides (now with the divisor considered "higher" than the dividend), is the dual Q∂ of Q. The converse of |, |-1, relates two integers if one divides the other, but unlike | it classifies the numerically-smaller integer as the "higher" one by this relation, so that for this order 2⊑1, for example. Q∂ is shown in Figure 8. In Q, 4⊑8, so we know without looking at Figure 8 that in Q∂, the dual statement 4⊒8 holds in the relation for that ordered set.

Extrema

Let S be an ordered set.

u∈S is said to be maximal in S iff there is no v∈S such that u≤v. A set may have any number of maximal elements, including zero. If u is S's only maximal element, then u is the maximum of S. The maximum element u (if it exists) is also called the top of S and is denoted by ⊤. Dually, t∈S is said to be minimal in S iff there is no s∈S such that s≤t. A set may have any number of minimal elements, including zero. If t is S's only minimal element, then t is the minimum of S. The minimum element t (if it exists) is also called the bottom of S and is denoted by ⊥.

Examples:

p∧q∧r is a maximal element of the set in Figure 6. Since it is the only maximal element, it is the maximum or top. The set in Figure 6 has three minimal elements (p, q, and r). It has no minimum (because it has three minimal elements). The set of all integers has no maximal or minimal elements (Figure 1). It has no maximum (because it has no maximal elements); similarly, it has no minimum. Bounds Upper bounds and LUBs

Figure 5 (again) The binary strings no longer than 3, ordered by the prefix relation (with prefix low)

Let S be an ordered set and let E⊆S.

y∈S is an upper bound of E iff x≤y for every x∈E. E may have no upper bound, one upper bound, or many. Note that y need not be an element of E in order to be an upper bound of E. We write Eu to denote the set of all upper bounds of E. Eu may be empty, a singleton, or have many members. If Eu is non-empty and has a minimum element u, then u is called the least upper bound (LUB) of E, written ∨E. The LUB of E is also called the supremum or join of E. In the common case where E consists of exactly two elements s and t, we can also write s∨t (pronounced "the least upper bound of s and t" or "s join t").

Examples, using the ordered set of Figure 5 as S:

Consider E={01}. E has several upper bounds in S, 01 itself, 010, and 011, so EU={01,010,011}. EU has a minimum element under the prefix relation ≤, and that minimum is 01, so E={01} has a LUB of 01 in S. Consider E={00,01}. There is no element of S that is greater than both 00 and 01. E thus has no upper bound in S, and EU is empty. EU has no minimum element under the prefix relation ≤ (because it has no elements at all), so E has no LUB in S. Lower bounds and GLBs

The dual concept for upper bound is lower bound, and analogous definitions apply.

z∈S is a lower bound of E iff z≤x for every x∈E. Note that z need not be an element of E in order to be a lower bound of E. We write El to denote the set of all lower bounds of E. If El is non-empty and has a maximum element v, then v is called the greatest lower bound (GLB) of E, written ∧E. The GLB of E is also called the infimum or meet of E. In the common case where E consists of exactly two elements s and t, we can also write s∧t (pronounced "the greatest lower bound of s and t" or "s meet t").

Examples:

(Figure 5) 000 ∨ 001 is 00. (Figure 3) { scrambled eggs, Jane Eyre } has no GLB because it has no lower bound at all. Existence of LUBs and GLBs

A LUB (GLB) can fail to exist for either of two reasons:

There may be no upper (lower) bound at all; Eu (El ) may be empty (for example, the binary strings in Figure 5 and {000, 001}). There may be upper (lower) bounds, but no least upper bound (greatest lower bound). There may be two or more minimal upper bounds (maximal lower bounds) that are not comparable, so that neither can be least (greatest) (for example, the divisibility ordering in Figure 7 and {2, 3}); or There may be an infinite descending (ascending) chain of upper (lower) bounds, so that none is minimal (maximal) (for example, as in the case of the reals with

【本文地址】

公司简介

联系我们